package com.smh;

import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author shiminghui
 * @date 2025/3/13 19:36
 * @description: TODO
 */
public class _041_sort_test {
    @Test
    public void test1() {
        int[] arr1 = {2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19};
        int[] arr2 = {2, 3, 7, 6};
        int[] ints = relativeSortArray(arr1, arr2);
        System.out.println(Arrays.toString(ints));
    }

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) {
            map.put(arr2[i], 0);
        }
        int[] ints = new int[arr1.length];
        int intIndex = 0;
        for (int i : arr1) {
            if (map.containsKey(i)) {
                map.put(i, map.get(i) + 1);
            } else {
                ints[intIndex++] = i;
            }
        }
        int[] res = new int[arr1.length];
        int index = 0;
        for (int i : arr2) {
            int count = map.get(i);
            for (int j = 0; j < count; j++) {
                res[index++] = i;
            }
        }
        // 排序list,升序
        Arrays.sort(ints);
        System.arraycopy(ints, index, res, index, ints.length - index);
        return res;
    }

    public int[] relativeSortArray2(int[] arr1, int[] arr2) {
        int max = arr1[0];
        for (int i = 1; i < arr1.length; i++) {
            max = Math.max(max, arr1[i]);
        }
        int[] count = new int[max + 1];
        for (int i = 0; i < arr1.length; i++) {
            count[arr1[i]]++;
        }
        int index = 0;
        for (int i = 0; i < arr2.length; i++) {
            while (count[arr2[i]] > 0) {
                arr1[index++] = arr2[i];
                count[arr2[i]]--;
            }
        }
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr1[index++] = i;
                count[i]--;
            }
        }
        return arr1;
    }

    /**
     * 给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。
     *
     * @param nums
     * @return
     */
    public int[] frequencySort(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        /*HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        List<Map.Entry<Integer, Integer>> list = map.entrySet().stream().sorted((o1, o2) -> {
            if (o1.getValue() == o2.getValue()) {
                return o2.getKey() - o1.getKey();
            } else {
                return o1.getValue() - o2.getValue();
            }
        }).toList();
        int index = 0;
        for (int i = 0; i < list.size(); i++) {
            Map.Entry<Integer, Integer> entry = list.get(i);
            int count = entry.getValue();
            int key = entry.getKey();
            while (count > 0) {
                nums[index++] = key;
                count--;
            }
        }*/
        int[] count = new int[max - min + 1];
        for (int i = 0; i < nums.length; i++) {
            count[nums[i] - min]++;
        }
        final int min1 = min;
        int[] array = Arrays.stream(nums).boxed().sorted((o1, o2) -> {
            if (count[o1 - min1] == count[o2 - min1]) {
                return o2 - o1;
            } else {
                return count[o1 - min1] - count[o2 - min1];
            }
        }).mapToInt(Integer::intValue).toArray();
        return array;
    }


    /**
     * 给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。
     * <p>
     * 您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。
     */
    public int maximumGap(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        if (max == min) {
            return 0;
        }
        // 使用桶排序的话,通的数量太多了,所以要想方法限制桶的个数
        /**
         * (max - min) / range +1 = nums.length
         * (max - min) / (nums.length - 1) = range
         */
        int range = Math.max((max - min) / (nums.length - 1), 1);
        int bucketNum = (max - min) / range + 1;
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketNum);
        // 创建桶
        for (int i = 0; i < bucketNum; i++) {
            buckets.add(new ArrayList<>());
        }

        for (int num : nums) {
            int index = (num - min) / range;
            buckets.get(index).add(num);
        }

        for (ArrayList<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }
        // 合并
        int index = 0;
        for (int i = 0; i < buckets.size(); i++) {
            ArrayList<Integer> bucket = buckets.get(i);
            for (int j = 0; j < bucket.size(); j++) {
                nums[index++] = bucket.get(j);
            }
        }

        // 使用基数排序,效率也不高
        /*int bucketNum = 10;
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(10);

        for (int i = 0; i < bucketNum; i++) {
            buckets.add(new ArrayList<>());
        }
        int lun = 1;
        while ((max = max/10) != 0){
            lun++;
        }


        for (int i = 0; i<lun;i++){
            for (int j = 0; j < nums.length; j++) {
                // 10 的i次方
                int index = nums[j] / (int) Math.pow(10, i) % 10;
                buckets.get(index).add(nums[j]);
            }
            int index = 0;
            for (int j = 0; j < buckets.size(); j++) {
                ArrayList<Integer> bucket = buckets.get(j);
                for (int k = 0; k < bucket.size(); k++) {
                    nums[index++] = bucket.get(k);
                }
                bucket.clear();
            }
        }*/


        int maxGap = 0;
        for (int i = 1; i < nums.length; i++) {
            maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);
        }
        return maxGap;
    }

    private int maximumGap1(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        if (max == min) {
            return 0;
        }
        // 使用桶排序的话,通的数量太多了,所以要想方法限制桶的个数
        // 并且保证肯定有一个桶是空的
        // (max - min) / range +1 = nums.length +1;
        // (max - min) / nums.length = range
        int range = Math.max((max - min) / nums.length, 1);
        int bucketNum = (max - min) / range + 1;
        Bucket[] buckets = new Bucket[bucketNum];
        for (int i = 0; i < bucketNum; i++) {
            buckets[i] = new Bucket();
        }
        for (int num : nums) {
            int index = (num - min) / range;
            buckets[index].add(num);
        }

        // 此时桶里面保留了桶里面的最大值和最小值
        int maxGap = 0;
        int lastMax = buckets[0].max;
        for (int i = 1; i < buckets.length; i++) {
            if (buckets[i].min != Integer.MAX_VALUE) {
                maxGap = Math.max(maxGap, buckets[i].min - lastMax);
                lastMax = buckets[i].max;
            }
        }
        return maxGap;
    }

    @Test
    public void test10() {
        int[] ints = {1, 10_000_000};
        System.out.println(maximumGap1(ints));
    }

    private class Bucket {
        int min;
        int max;

        public Bucket() {
            min = Integer.MAX_VALUE;
            max = Integer.MIN_VALUE;
        }

        public void add(int num) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
    }
}
